package com.pointstar.dp.tree;

/**
 * 南软2007T1
 * 南软2008T1、2013T1
 * 验证二叉搜索树
 *
 * @author 朱科睿
 */
public class BinarySearchService {

    static long pre = Long.MIN_VALUE;

    /**
     * 南软2007T1
     * 思路：中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false。
     *
     * @param root 二叉树根节点
     * @return 如果{@code true}，则是二叉搜索树
     */
    private static boolean isValidBST(BinarySearch root) {

        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.getLeft())) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回false；否则继续遍历。
        if (root.getData() <= pre) {
            return false;
        }
        pre = root.getData();
        // 访问右子树
        return isValidBST(root.getRight());
    }

    /**
     * 南软2008T1、2013T1
     * 递归遍历二叉搜索树，按照降序输出比指定值num大的节点值
     * Note：
     *     降序输出，则先遍历右子树，再遍历左子树；
     *     升序输出，则先遍历左子树，再遍历右子树。
     *
     * @param root 根节点
     * @param num  指定值
     */
    private static void matchLargeNum(BinarySearch root, int num) {

        if (root != null) {
            matchLargeNum(root.getRight(), num);
            if (root.getData() >= num) {
                System.out.print(root.getData() + " ");
            }
            matchLargeNum(root.getLeft(), num);
        }
    }

    public static void main(String[] args) {
        BinarySearch third1 = new BinarySearch(2);
        BinarySearch third3 = new BinarySearch(5);
        BinarySearch second2 = new BinarySearch(6);
        second2.setLeft(third3);
        BinarySearch second1 = new BinarySearch(3);
        second1.setLeft(third1);
        BinarySearch root = new BinarySearch(4);
        root.setLeft(second1);
        root.setRight(second2);

        System.out.println(isValidBST(root));
        matchLargeNum(root, 4);
    }

}
